3.6 Asymptotic Analysis

“But if there’s something that frightens you, there are those that turn their eyes away and there are those who try to see through the fear and conquer it.” - The Big O

Computer Science classes often study the performance of algorithms through the lens of Asymptotic Analysis. Many proofs in asymptotic analysis are sloppy; we take shortcuts, work with approximations, and almost never refer back to the official definitions. The only excuse is that, in practice, this still usually produces the right answer! In this section, we’ll be careful and precise about asymptotic analysis, which is great practice for writing proofs and working with quantifiers.

If \(f\) and \(g\) are functions from \(\mathbb{N}\) to \(\mathbb{N}\), we say \[ f \in O(g) \quad\mathrm{iff}\quad \exists c{>}0\ \ \exists m{\geq 0}\ \ \forall i{\geq}m\ \ (\,f(i) \leq c\cdot g(i)\,) \] (where \(c\) is a real number, and \(m\) and \(i\) are natural numbers).

That is, \(f\in O(g)\) is true iff \(f\) stays below the scaled function \(c\cdot g\) once we reach inputs larger than \(m\).

Intuitively, \(f\in O(g)\) means that \(f\) grows no faster than [a constant multiple of] \(g\) as the input value becomes arbitrarily large.

Theorem: \(2n+1 \in O(n)\). \(\qquad\) That is to say, \((\,n \mapsto 2n{+}1\,) \in O(\, n\mapsto n\,)\). > >Proof (heavily annotated): > To show: \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,2i{+}1 \leq c\,i\,)\)
>Put \(c := 3\) and \(m := 2\).
\(\quad\) To show: \(\color{green} \forall i{\geq}m\ \ \ (\,2i{+}1 \leq c\,i\,)\)
>\(\quad\) Let \(i \geq m = 2\) be given.
\(\qquad\) To show: \(\color{green}2i{+}1 \leq c\,i\)
\(\qquad\) Then \(2i+1 \leq 2i + i = 3i = c\,i\)
>\(\quad\) Thus: \(\color{green} \forall i{\geq}m\ \ (\,2i{+}1\leq c\,i\,)\)
So \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,2i{+}1 \leq c\,i\,)\)
Therefore, \(2n+1 \in O(n)\). QED > >— > >Proof (traditional compressed form): >Put \(c := 3\) and \(m := 2\). Then for all \(i \geq m = 2\), \(2i+1 \leq 2i + i = 3i = c\,i\) as required. QED

There are three things to note about this example:

1. The annotated proof is much more verbose then you would ever see in a real-life proof. But when first practicing these proofs, the annotations are extremely helpful to keep track of where we are in the proof, and where we should be going.
2. One might wonder how we knew that \(c\) should be 3 and \(m\) should be 2. The answer is that the author of this proof didn’t know when the proof was first being constructed; it was only after playing around with the algebra that follows that it became clear that 3 and 2 would ensure that \(2i+1 \leq c\,i\) for all \(i\geq m\). The order that the proof is presented is often not the order in which the pieces were figured out!
3. Infinitely many other choices of \(c\) and \(m\) would have worked as well (though not all of choices). However, since we are proving an existentially quantified formula, it suffices to find a single example that works.

Theorem: \(100n+1000 \in O(n)\).
That is to say, \((\,n \mapsto 100n{+}1000\,) \in O(\, n\mapsto n\,)\). > Proof (heavily annotated):
To show: \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,100i{+}1000 \leq c\,i\,)\)
Put \(c := 200\) and \(m := 10\).
\(\quad\) To show: \(\color{green} \forall i{\geq}m\ \ \ (\,100i{+}1000 \leq c\,i\,)\)
\(\quad\) Let \(i \geq m = 10\) be given.
\(\qquad\) To show: \(\color{green} 100i{+}1000 \leq c\,i\)
\(\qquad\) Then \(10 \leq i\),
\(\qquad\) so \(1000 \leq 100i\),
\(\qquad\) and hence \(100i + 1000 \leq 200 i = ci\)
\(\quad\)Thus: \(\color{green} \forall i{\geq}m\ \ \ (\,100i{+}1000 \leq c\,i\,)\)
So \(\color{green}\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,100i{+}1000 \leq c\,i\,)\)
Therefore, \(100n+1000 \in O(n)\). QED

If \(f\) and \(g\) are functions from \(\mathbb{N}\) to \(\mathbb{N}\), we define the function \(f+g\) “pointwise.” That is, for every \(k\in\mathbb{N}\), \[ (f+g)(k) := f(k) + g(k) \]

Theorem: If \(f\in O(h)\) and \(g\in O(h)\) then \(f+g \ \in \ O(h)\). > Proof (heavily annotated): > To show: \(\color{green} \forall f,g:{\mathbb{N}{\to}\mathbb{N}}\ \ \ (\,f{\in}O(h)\land g{\in}O(h) \ \to \ f{+}g\in O(h)\,)\)
Let \(f\in O(h)\) and \(g\in O(h)\) be given.
That is, assume that \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,f(i) \leq c\, h(i)\,)\)
and that \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,g(i) \leq c\, h(i)\,)\) .
\(\quad\) To show: \(\color{green} f{+}g\in O(h)\)
\(\quad\) That is, to show: \(\color{green} \exists c{>}0\ \ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,)\)
\(\quad\) By assumption, there exist \(c_1\) and \(m_1\) such that \(\forall i{\geq}m_1\ \ (\,f(i) \leq c_1\, h(i)\,)\)
\(\quad\) and there exist \(c_2\) and \(m_2\) such that \(\forall i{\geq}m_2\ \ (\,g(i) \leq c_2\, h(i)\,)\).
\(\quad\) Put \(c := c_1 + c_2\)
\(\quad\) and \(m := \max\{m_1, m_2\}\)
\(\qquad\) To show: \(\color{green} \forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,)\)
\(\qquad\) Let \(i \geq m\) be given.
\(\qquad\) To show: \(\color{green} f(i){+}g(i) \leq c\, h(i)\)
\(\quad \qquad\) Since \(i \geq m \geq m_1\), \(f(i) \leq c_1\, h(i)\).
\(\quad \qquad\) Since \(i \geq m \geq m_2\), \(g(i) \leq c_2\, h(i)\).
\(\quad \qquad\) So \((f+g)(i) = f(i)+g(i) \leq (c_1+c_2)\,h(i) = c\, h(i)\).
\(\qquad\) Thus \(\color{green} \forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,)\)
\(\quad\) Then \(\color{green} \exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,f(i){+}g(i) \leq c\, h(i)\,)\)
>So \(\color{green} \forall f,g:{\mathbb{N}{\to}\mathbb{N}}\ \ \ (\,f{\in}O(h)\land g{\in}O(h) \ \to \ f{+}g\in O(h)\,)\)
Therefore, \(f+g \in O(h)\) for all \(f\) and \(g\). QED.

Previous: 3.5 Proofs with Quantifiers

Next: 4.1 Logic Programming